package com.kevinkk.dp;

/**
 * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
 * 你可以对一个单词进行如下三种操作：
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 */

public class EditDistance {
    class Solution {
        public int minDistance(String word1, String word2) {
            char[] c1 = word1.toCharArray(), c2 = word2.toCharArray();
            int[][] dp = new int[c1.length + 1][c2.length + 1];
            // 初始化
            for (int i = 1; i <= c1.length; i++) dp[i][0] = i;
            for (int i = 1; i <= c2.length; i++) dp[0][i] = i;

            for (int i = 1; i <= c1.length; i++) {
                for (int j = 1; j <= c2.length; j++) {
                    if (c1[i - 1] == c2[j - 1]) {
                        // 不用操作
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        // dp[i - 1][j], dp[i][j - 1] 表示删除操作
                        // dp[i - 1][j - 1] 表示添加操作
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                }
            }

            return dp[c1.length][c2.length];
        }
    }
}
